package dp;

/**
 * @author wcj
 * @Date 2021/7/6 17:01
 * @Version 1.0
 */
public class MaxSymmetryStr {

    /**
     * 最长回文子串：回文的特征就是去头去尾还是回文
     * 动态规划：
     * ①状态定义：dp[i][j]表示从第i个字符到第j个字符是不是回文子串
     * ②状态转移方程：
     * dp[i][j] = true,i==j
     * dp[i][j] = s.charAt(i) == s.charAt(j),j-i==1
     * dp[i][j] = s.charAt(i)==s.charAt(j) && dp[i+1][j-1]  j-i>=2
     * ③状态初始化
     * 需要注意的点是：我们需要从左到右进行递推，例如dp[0][3]需要从dp[1][2]进行地推过来
     *
     * @param s
     * @return
     */
    public static String maxSymmetryStr(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int max = 0;
        int left = 0;
        int right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (j - i == 1) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                }
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    left = i;
                    right = j + 1;
                }
            }
        }
        return s.substring(left, right);
    }
}
